import java.util.List;

public class test {
    /*链表分割 描述
    现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
    且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here
            ListNode cur = pHead;
            ListNode bs = null;
            ListNode be = null;
            ListNode as = null;
            ListNode ae = null;
            while (cur != null) {
                if (cur.val < x) {
                    if (bs == null) {
                        bs = cur;
                        be = cur;
                    } else {
                        be.next = cur;
                        be = be.next;
                    }
                } else {
                    if (as == null) {
                        as = cur;
                        ae = cur;
                    } else {
                        ae.next = cur;
                        ae = ae.next;
                    }

                }
                cur = cur.next;
            }
            if (bs == null) {
                return as;
            }
            be.next = as;
            if (as != null) {
                ae.next = null;

            }
            return bs;
        }
        链表的回文结构
        对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true*/
import java.util.*;

    /*
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public class PalindromeList {
        public boolean chkPalindrome(ListNode head) {
            // write code here
            if(head == null){return true;}
            // 找到中间结点
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            //反转
            ListNode cur = slow.next;
            while(cur != null){
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //一个向前走 一个先后走
            while(slow != head){

                if(slow.val != head.val){
                    return false;
                }
                //偶数情况
                if(head.next == slow){
                    return true;
                }

                head = head.next;
                slow = slow.next;
            }
            return true;
        }
    }
    判定链表相交
    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
    如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：



题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;//pl永远指向最长的链表
        ListNode ps = headB;
        //1.分别求长度
        int lenA = 0;int lenB = 0;
        while(pl!= null){
            lenA++;
           pl =pl.next;
        }
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
      int len = lenA -lenB;
      if(len < 0){
          pl = headB;
          ps = headA;
          len = lenB -lenA;
      }
      //保证pl指向最长的 ps指向最短的  len一定是正数
        //2、让pl先走len步
      while(len != 0){
          pl = pl.next;
          len--;
      }
       //3. 一人 一步走
      while(pl != null && ps != null && pl != ps){
          pl = pl.next;
          ps = ps.next;
      }
      if(pl == ps && pl == null){
          return null;
      }
        return pl;
    }
}
判断链表带环
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}
求环的入口点
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast =fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if( fast == null || fast.next == null){
            //因为循环条件退出
            return null;//证明连环都没有
        }
        slow = head;
        while( slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
         return slow;
    }
}
     */
    }

}
